The present invention relates generally to the field of data communications and in particular to a method and system for interleaving and de-interleaving data in a data communications system.
Digital data communication systems are commonly used to transmit and receive data transmitted between remote transmitting and receiving locations. A central facet of any data communications system is the reliability and integrity of the data communicated. Ideally, the data, received at the receiving location should be identical to the data transmitted from the transmitting location. Practically however, a noisy transmission medium can cause the data which is being received to be corrupted or lost with respect to the originally transmitted data.
Early data communications systems utilized simple error detection and correction schemes to compensate for noise on a communications medium. A widely utilized method of error detection included the use of a parity bit in each block of transmitted data to indicate whether the particular block contained an odd or even number of high bits, i.e., bits equal to one. By determining whether the total number of high bits was even or odd and comparing the result to the value of the parity bit, a data receiver determined if the transmitted data blocks contained errors. This relatively simple scheme has numerous disadvantages such as its ability to detect only one inaccurate bit in a data block. Moreover, parity bit error detection cannot be used to correct a bit in error. Upon receiving a bit in error, a data receiver using parity bit error detection is limited to requesting retransmission of the data block in error from a data transmitter.
Other early methods and systems for error detection and correction included the use of a voting consensus circuit. Using a voting consensus circuit, a data transmitter transmitted a single data block multiple times to a data receiver. A data receiver included a voting circuit that would compare the multiple received versions of the same data block transmitted by the data transmitter and determine which, if any, of the transmitted data blocks was the correct, i.e., non-corrupted, data block. While a voting circuit reduced the number of retransmission requests issued by a transmitter as compared to a system utilizing parity bits, a voting consensus circuit system suffered from speed and throughput constraints due to repeated transmission of the same data.
The above-mentioned error correction and detection schemes are examples of binary block codes. More particularly, an (n,k,d) binary block code includes a series of 2k binary codewords of block length n and minimum distance d, i.e., coding distance. Using binary block codes, a datastream to be transmitted is partitioned into binary blocks of length k which are then mapped into binary codewords of length n and then modulated and transmitted through a communication medium. As is known in the art, these schemes are limited to correcting up to (dxe2x88x921)/2 bit errors within each codeword.
The limitations of the above-described systems become evident when considering the nature of noisy transmission media. Frequently, noise in a communications medium occurs in non-frequent bursts. Thus, where blocks of data are transmitted in sequence, a burst of noise may corrupt a block of data beyond the capabilities of the above-mentioned schemes to correct the errors, i.e., a burst of noise may corrupt more than (dxe2x88x921)/2 bits of data in a codeword, thus rendering error correction schemes, such as those described above, ineffective.
Interleaver/de-interleaver systems have been developed to address and compensate for the effects of noise bursts over transmission media. An interleaver accepts a datastream to be transmitted and interleaves or co-mingles the data from several codewords in a predetermined manner such that the co-mingled data can be re-organized and the datastream reconstructed by a de-interleaver at the receiving end. In other words, instead of transmitting a succession of complete codewords, the interleaver transmits a portion (also referred to as a symbol), e.g., a byte, of a first codeword then transmits a portion of a second codeword and so on. By processing a datastream through an interleaver before it is modulated and transmitted through a communications media or channel, the effects of non-periodic noise bursts are minimized because noise encountered in the transmission medium is distributed among several codewords of the reconstructed or de-interleaved datastream.
An interleaver/de-interleaver system requires two known values, the total number of symbols (N) in each codeword of the non-interleaved datastream and the depth (D) of the interleaver. The size of a symbol is measured in bits and is preferably equal to one byte, i.e., eight bits. The depth of the interleave (D) represents the total number of non-interleaved codewords that are represented in any one interleaved codeword.
Viewing a simple interleaver/de-interleaver system logically, the symbols of the datastream to be transmitted are written to an (N,D) two dimensional memory of the interleaver in columns and are read out from the two dimensional memory of the interleaver in rows. The write and read operations are performed in groups of symbols rather than being alternated between each symbol. This type of interleaving is known in the art as block interleaving and introduces a latency in transmission of one (N*D) block at the interleaver. Furthermore, block interleaving requires two blocks of memory (2*N*D) at the interleaver and two blocks of memory (2*N*D) at the de-interleaver.
Thus, it can be seen from the above description of block interleaving that an interleaver/de-interleaver system requires memory storage units to store symbols at both the transmitting (interleaving) end and the receiving (de-interleaving) end of the transmission medium. Because the codewords in an interleaved datastream are not arranged in the same sequential time order as the non-interleaved datastream, an interleaver requires a sufficient amount of memory to store the input symbols of the non-interleaved codewords which are not immediately transmitted in the interleaved datastream. Similarly, a de-interleaver requires a sufficient amount of memory to store the input symbols of the interleaved codewords which are not immediately placed into the non-interleaved datastream. Memory requirements are, therefore, an important factor to be considered in designing interleaver/de-interleaver systems.
One type of prior art interleaver/de-interleaver system and method which reduces the amount of necessary memory over that required in block interleaving is a convolutional interleaver/de-interleaver system and method disclosed by John L. Ramsey in xe2x80x9cRealization of Optimum Interleaverxe2x80x9d, I.E.E.E. Transactions on Information Theory, Vol. IT-16, No. 3, May 1970, which is hereby incorporated herein by reference in its entirety. In convolutional interleaving and de-interleaving, the write and read operations of the interleaver and de-interleaver are alternated on a symbol basis rather than being carried out in groups of symbols as in block interleaving.
Each of the convolutional interleaving techniques described by Ramsey utilizes a tapped shift register and a commutator to accomplish the convolutional interleaving described therein. More particularly, four techniques for convolutional interleaving are described by Ramsey. As discussed therein, the convolutional techniques known in the art at that time, although achieving minimum possible end to end latency, were wasteful of storage insofar as, during the interleaving process, many of the symbols stored in later shift register stages were already read into the output sequence of the convolutional interleaver. Ramsey described a technique of reducing the required storage capacity of a convolutional interleaver without changing the functionality of the convolutional interleaver. Furthermore, the convolutional interleaver disclosed by Ramsey reduces the amount of memory required in an interleaver or a de-interleaver to (0.5*N*D) symbols, i.e., xc2xc that required by block interleaving.
As is known in the art, modern convolutional interleaver/de-interleaver systems and methods, such as that disclosed in U.S. Pat. No. 5,636,224 of Voith, et al., which is hereby incorporated by reference herein in its entirety, utilize electronic memory in conjunction with control logic as memory storage units in interleavers and de-interleavers rather than shift registers and commutators. The memory units in an interleaver are configured in an electronic memory as First In First Out (FIFO) buffers to which symbols of the input non-interleaved datastream are written and from which symbols of the interleaved datastream are read. Likewise, the memory units in a de-interleaver are configured in an electronic memory as FIFOs to which symbols of the input interleaved datastream are written and from which symbols of the non-interleaved datastream are read. More particularly, N FIFOs are utilized in each of the interleaver and de-interleaver.
Implementing FIFOs in addressable electronic memory requires that addresses, pointers and boundaries be calculated and stored for each of the FIFOs. Essentially, the complexity, the memory occupied and the process power required with the prior art approach, is directly proportional to N. What is desired, therefore, is a convolutional interleaver/de-interleaver method and system that utilizes a minimal number of FIFOs.
In accordance with a first embodiment of the present invention, a method for interleaving or de-interleaving a datastream of codewords divided into indexed symbols includes allocating an electronic memory into a predetermined number of FIFOs equal to the desired depth (D) of the interleave operation. Thereafter, for each symbol of each codeword to be operated upon, the method performs the following: (1) determines a first operational index of the symbol corresponding to the position of the symbol within a non-interleaved codeword; (2) performs a first operation upon one of the FIFOs identified by the first operational index of the symbol and a first predetermined criteria defining the location of the symbol in the electronic memory; (3) determines a second operational index of a corresponding symbol in an interleaved codeword; and (4) performs a second operation upon one of the FIFOs identified by the second operational index and a second predetermined criteria defining the location of the corresponding symbol in the electronic memory.
In accordance with a second embodiment of the present invention, a method for interleaving or de-interleaving a datastream of codewords divided into indexed symbols includes allocating an electronic memory into a predetermined number of FIFOs equal to the desired depth (D) of the interleave operation. Thereafter, for each codeword to be operated upon, the method performs the following: (1) for each of the symbols in the codeword, (a) determines a first operational index of the symbol corresponding to the respective position of the symbol within a non-interleaved codeword, and (b) performs a first operation upon one of the FIFOs identified by the first operational index of the symbol and a first predetermined criteria defining the location of the symbol in the electronic memory; and (2) for each of the symbols of the codeword, (a) determines a second operational index of a corresponding symbol in an interleaved codeword, and (b) performs a second operation upon one of the FIFOs identified by the second operational index and a second predetermined criteria defining the location of the corresponding symbol in the electronic memory.
A first embodiment of an interleaver system according to the present invention includes: (1) an electronic memory which is configured into a predetermined number of FIFOs wherein each FIFO outputs data in the order in which data is input; (2) an input port which receives a non-interleaved datastream of input codewords divided into indexed symbols; (3) an output port which transmits an interleaved datastream of output interleaved codewords; and (4) a control unit which configures the electronic memory into one of a predetermined number of FIFOs of predetermined size, the predetermined number of FIFOs being equal to the depth of the desired interleave. For each of the input symbols, the control unit further:
a) determines a first operational index of the symbol;
b) writes the symbol in one of the FIFOs identified by the first operational index using a first predetermined criteria defining the location of the symbol in the electronic memory;
c) determines a second operational index of a corresponding output symbol; and
d) reads a symbol stored in one of the FIFOs identified by the second operational index using a second predetermined criteria defining the location of the corresponding symbol in the electronic memory.
A second embodiment of an interleaver system according to the present invention includes: (1) an electronic memory which is configured into a predetermined number of FIFOs wherein each FIFO outputs data in the order in which data is input; (2) an input port which receives a non-interleaved datastream of input codewords divided into indexed symbols; (3) an output port which transmits an interleaved datastream of output codewords; and (4) a control unit which configures the electronic memory into one of a predetermined number of FIFOs of predetermined size, the predetermined number of FIFOs being equal to the desired depth of the interleave. For each of the input codewords, the control unit further:
a) for each of the symbols of the input codeword,
i) determines a first operational index of the symbol, and
ii) writes the symbol into a FIFO identified by the first operational index of the symbol using a first predetermined criteria defining the location of the symbol in the electronic memory; and
b) for each of the symbols of the output codeword,
i) determines a second operational index of the output symbol; and
ii) reads a symbol stored in a FIFO identified by the second operational index using a second predetermined criteria defining the location of the symbol in the electronic memory.
A first embodiment of a de-interleaver system according to the present invention includes: (1) an electronic memory which is configured into a predetermined number of FIFOs wherein each FIFO outputs data in the order in which data is input; (2) an input port which receives an interleaved datastream of input codewords divided into indexed symbols; (3) an output port which outputs a non-interleaved datastream of output codewords; and (4) a control unit which configures the electronic memory into one of a predetermined number of FIFOs of predetermined size, the predetermined number of FIFOs being equal to the desired depth of the interleave. For each of the output symbols, the control unit further:
a) determines a first operational index of the symbol;
b) reads the symbol from the FIFO identified by the first operational index using a first predetermined criteria defining the location of the symbol in the electronic memory;
c) determines a second operational index of a corresponding input symbol; and
d) writes an input symbol to one of the FIFOs identified by the second operational index using a second predetermined criteria defining the location of the corresponding symbol in the electronic memory.
A second embodiment of a de-interleaver system according to the present invention includes: (1) an electronic memory which is configured into a predetermined number of FIFOs wherein each FIFO outputs data in the order in which data is input; (2) an input port which receives an interleaved datastream of input codewords divided into indexed symbols; (3) an output port which outputs a non-interleaved datastream of output codewords; and (4) a control unit which configures the electronic memory into one of a predetermined number of FIFOs of predetermined size, the predetermined number of FIFOs being equal to the desired depth of the interleave. For each of the output codewords, the control unit further:
a) for each of the symbols of the output codeword,
i) determines a first operational index of the symbol, and
ii) reads the symbol of the output codeword from a FIFO identified by the first operational index of the symbol using a first predetermined criteria defining the location of the symbol in the electronic memory; and
b) for each of the symbols of the input codeword,
i) determines a second operational index of the input symbol; and
ii) writes a symbol to a FIFO identified by the second operational index using a second predetermined criteria defining the location of the symbol in the electronic memory.